Voice mail is a useful business and personal tool that allows callers to leave voice messages when the called party is not available to take an incoming call. Voice mail has been implemented by telephone service providers, both wireline and wireless, as a common feature provided to their users. In a typical application, if a communication device associated with a user (e.g., a subscriber of the telephone service) is not available, or if the user does not respond to or accept a call received over the communication network, the call may be forwarded to a Voice Mail System (VMS). The VMS then records a voice message from the caller, stores the message in a mailbox associated with subscriber the user's identifier (e.g. phone number) for later retrieval by the user, or forwards the stored message to the communication device when it becomes available in the network. A message notification is provided to indicate that a voice message is available for the user.